#include <stdio.h>
#include <stdlib.h>

typedef struct Graph{
    char *vexs;
    int **arcs;
    int vexNum;
    int arcNum;
} Graph;

#define MAX 32767

Graph *initGraph(int vexNum) //顶点数
{
    Graph *G = (Graph *)malloc(sizeof(Graph));
    G->arcs = (int **)malloc(sizeof(int *) * vexNum);
    G->vexs = (char *)malloc(sizeof(char) * vexNum);
    for (int i = 0; i < vexNum; i++) {
        G->arcs[i] = (int *)malloc(sizeof(int) * vexNum);
    }
    G->arcNum = 0;
    G->vexNum = vexNum;
    return G;
}

void createGraph(Graph *G, char *vexs, int *arcs)
{
    for (int i = 0; i < G->vexNum; i++) {
        G->vexs[i] = vexs[i];
        for (int j = 0; j < G->vexNum; j++) { //注意此时只是普通的二级指针
            G->arcs[i][j] = *(arcs + i * G->vexNum + j);
            if (G->arcs[i][j] > 0 && G->arcs[i][j] != MAX) {
                G->arcNum++;
            }
        }
    }
    G->arcNum /= 2;
}

void DFS(Graph *G, int *visited, int index) //索引第一个节点开始
{
    printf("%c ", G->vexs[index]);//访问
    visited[index] = 1;
    for (int i = 0; i < G->vexNum; i++) {
        if (G->arcs[index][i] > 0 && G->arcs[index][i] != MAX && !visited[i]) {//遍历 + 递归
            DFS(G, visited, i);
        }
    }
}

/**
 * 这个算法也被称为3for算法 n个点 从n到n不断更新 总共三重循环
 * 1. 初始化d和p两个二维数组 d表示两点最短路径长度 p表示两点后一点前驱
 * 2. 不断更换中继点1-n 更新前驱数组
*/

void floyd(Graph *G)
{
    //1.初始化
    int d[G->vexNum][G->vexNum];
    int p[G->vexNum][G->vexNum];
    for (int i = 0; i < G->vexNum; i++) {
        for (int j = 0; j < G->vexNum; j++) {
            d[i][j] = G->arcs[i][j]; //此时d直接赋值就行
            if (G->arcs[i][j] > 0 && G->arcs[i][j] != MAX) { //有弧
                p[i][j] = i;
            } else {
                p[i][j] = -1; //没有前驱置为-1
            }
        }
    }
    //2. 3for 不断更新d和s数组
    for (int i = 0; i < G->vexNum; i++) {
        for (int j = 0; j < G->vexNum; j++) {
            for (int k = 0; k < G->vexNum; k++) {
                //这里也可以添加判断条件毕竟n到n的最短路径就是0 而且自己作为中继点不会是起点和终点
                //可排除主对角线和i行i列
                if (d[j][i] + d[i][k] < d[j][k]) {
                    d[j][k] = d[j][i] + d[i][k];
                    p[j][k] = p[i][k];//这里注意此时可不能用p[j][k] = i;递推的方式处理 不过又好像行算了不管了
                }
            }
        }
    }
    //这里只是遍历d和p数组
    for (int i = 0; i < G->vexNum; i++) {
        for (int j = 0; j < G->vexNum; j++) {
            printf("%d ", d[i][j]);
        }
        putchar('\n');
    }
    putchar('\n');
    for (int i = 0; i < G->vexNum; i++) {
        for (int j = 0; j < G->vexNum; j++) {
            printf("%d ", p[i][j]);
        }
        putchar('\n');
    }
}

int main(void)
{
    Graph* G = initGraph(4);
    int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
    for (int i = 0; i < G -> vexNum; i++)
        visited[i] = 0;
    int arcs[4][4] = {
            0, 1, MAX, 3,
            1, 0, 2, 2,
            MAX, 2, 0, 8,
            3, 2, 8, 0
    };
    createGraph(G, "1234", (int*)arcs);
    DFS(G, visited, 0);
    putchar('\n');
    printf("\n");
    floyd(G);
    return 0;
}